package com.example.leetcode.tree.common;

import com.example.leetcode.array.common.ArrayUtils;
import com.example.leetcode.common.Result;
import com.example.leetcode.linkedlist.common.ListNode;
import javafx.util.Pair;
import lombok.extern.slf4j.Slf4j;

import java.util.*;
import java.util.stream.Collectors;

@Slf4j
public class TreeUtils {

    public static void levelOrder(TreeNode root) {
        if (root == null) return;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            System.out.print("第 " + level + " 层: ");
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                System.out.print(node.val + " ");
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            System.out.println();
            level++;
        }
    }

    public static void printTree(TreeNode root) {
        printTree(root, 0);
    }

    private static void printTree(TreeNode node, int depth) {
        if (node == null) return;

        printTree(node.right, depth + 1);

        for (int i = 0; i < depth; i++) {
            System.out.print("        "); // 8个空格对齐
        }
        System.out.println(node.val);

        printTree(node.left, depth + 1);
    }

    /**
     * 根据广度优先遍历序列生成二叉树
     *
     * @param list
     * @return
     */
    public static TreeNode generateAtreeByBFSList(List<Integer> list) {
        if (list == null || list.size() == 0) {
            return null;
        }
        System.out.println("开始生成二叉树=========");
        TreeNode root = new TreeNode();
        int i = 0;
        int j = 1;
        root.val = list.get(i); // 0
        root.level = 1;
        System.out.println("第" + j + "个节点," + root.val);
        i++;
        j++;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (true) {
            // 把队首元素取出来
            TreeNode currentNode = queue.poll(); // 0 1 2
            if (currentNode == null) {
                continue;
            }
            if (i > list.size() - 1) {
                break;
            }
            Integer currentLeftI = list.get(i);
            if (currentLeftI != null) {
                currentNode.left = new TreeNode(currentLeftI);
                System.out.println("第" + j + "个节点," + currentNode.left.val);
            } else {
                System.out.println("第" + j + "个节点," + currentNode.left);
            }
            queue.add(currentNode.left); // 1
            i++;
            j++;
            if (i > list.size() - 1) {
                break;
            }
            Integer currentRightI = list.get(i);
            if (currentRightI != null) {
                currentNode.right = new TreeNode(currentRightI);
                System.out.println("第" + j + "个节点," + currentNode.right.val);
            } else {
                System.out.println("第" + j + "个节点," + currentNode.right);
            }
            queue.add(currentNode.right); // 2
            i++;
            j++;
        }
        System.out.println("完成生成二叉树=========");
        TreeUtils.treeBFSTraverseWithLevelInfo(root);
        return root;
    }

    public static TreeNode generateLeetcodeTree(Integer[] nums) {
        List<Integer> list = ArrayUtils.arrayToList(nums);

        if (list == null || list.size() == 0) {
            return null;
        }
        TreeNode root = new TreeNode();
        int i = 0;
        root.val = list.get(i); // 0
        root.level = 1;
        i++;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (true) {
            // 把队首元素取出来
            TreeNode currentNode = queue.poll(); // 0 1 2
            if (currentNode == null) {
                continue;
            }
            if (i > list.size() - 1) {
                break;
            }
            Integer currentLeftI = list.get(i);
            if (currentLeftI != null) {
                currentNode.left = new TreeNode(currentLeftI);
            } else {
            }
            queue.add(currentNode.left); // 1
            i++;
            if (i > list.size() - 1) {
                break;
            }
            Integer currentRightI = list.get(i);
            if (currentRightI != null) {
                currentNode.right = new TreeNode(currentRightI);
            } else {
            }
            queue.add(currentNode.right); // 2
            i++;
        }
        return root;
    }

    public static Node generateLeetcodeTreeForNode(Integer[] nums) {
        List<Integer> list = ArrayUtils.arrayToList(nums);

        if (list == null || list.size() == 0) {
            return null;
        }
        Node root = new Node();
        int i = 0;
        root.val = list.get(i); // 0
        root.level = 1;
        i++;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (true) {
            // 把队首元素取出来
            Node currentNode = queue.poll(); // 0 1 2
            if (currentNode == null) {
                continue;
            }
            if (i > list.size() - 1) {
                break;
            }
            Integer currentLeftI = list.get(i);
            if (currentLeftI != null) {
                currentNode.left = new Node(currentLeftI);
            } else {
            }
            queue.add(currentNode.left); // 1
            i++;
            if (i > list.size() - 1) {
                break;
            }
            Integer currentRightI = list.get(i);
            if (currentRightI != null) {
                currentNode.right = new Node(currentRightI);
            } else {
            }
            queue.add(currentNode.right); // 2
            i++;
        }
        return root;
    }


    /**
     * 判断当前二叉树上的所有节点是否比指定参数小
     *
     * @param root
     * @param val
     * @return
     */
    public static boolean isAllLessThanVal(TreeNode root, int val) {
        if (root == null) {
            return true;
        }
        if (root.val < val && isAllLessThanVal(root.left, val) && isAllLessThanVal(root.right, val)) {
            return true;
        }
        return false;
    }

    /**
     * 判断当前二叉树上的所有节点是否比指定参数大
     *
     * @param root
     * @param val
     * @return
     */
    public static boolean isAllMoreThanVal(TreeNode root, int val) {
        if (root == null) {
            return true;
        }
        if (root.val > val && isAllMoreThanVal(root.left, val) && isAllMoreThanVal(root.right, val)) {
            return true;
        }
        return false;
    }

    /**
     * 对二叉树进行中序遍历，并将所有节点加入list中存储
     *
     * @param root
     * @param treeNodeList
     */
    public static void inOrderTraverseToList(TreeNode root, List<TreeNode> treeNodeList) {
        if (root == null) {
            return;
        }
        // 先将左子树加入list
        inOrderTraverseToList(root.left, treeNodeList);
        // 加入当前节点
        treeNodeList.add(root);
        System.out.println(root.val);
        // 加入右子树的所有节点
        inOrderTraverseToList(root.right, treeNodeList);
    }

    /**
     * 对二叉树进行中序遍历
     *
     * @param root
     */
    public static void inOrderTraverse(TreeNode root) {
        if (root == null) {
            return;
        }
        // 先将左子树加入list
        inOrderTraverse(root.left);
        // 加入当前节点
        System.out.println(root.val);
        // 加入右子树的所有节点
        inOrderTraverse(root.right);
    }

    /**
     * 对二叉树进行广度优先遍历，输出节点值和层数
     *
     * @param root
     */
    public static void treeBFSTraverseWithLevelInfo(TreeNode root) {
        System.out.println("对二叉树进行广度优先遍历，输出节点值和层数");
        if (root == null) {
            System.out.println("root为null");
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        root.level = 1;
        queue.add(root);
        while (queue.size() > 0) {
            // 输出队首节点
            TreeNode peek = queue.peek();
            if (peek != null) {
                System.out.println(peek.val + ", level = " + peek.level);
            } else {
                System.out.println(peek);
            }
            // 队首节点出队
            TreeNode currentNode = queue.poll();
            // 左右孩子为null时会进队列，但是当当前节点就是null时，不再添加左右孩子进队列
            if (currentNode != null) {
                // 当前节点的层数
                int currentLevel = currentNode.level;
                // 左孩子进队列
                TreeNode leftChild = currentNode.left;
                if (leftChild != null) {
                    // 如果原先的二叉树节点信息中包含了层数信息，不再添加层数
                    if (leftChild.level == 0) {
                        // 左孩子不为空，层数+1
                        leftChild.level = currentLevel + 1;
                    }
                }
                queue.add(leftChild);
                // 右孩子进队列
                TreeNode rightChild = currentNode.right;
                if (rightChild != null) {
                    // 如果原先的二叉树节点信息中包含了层数信息，不再添加层数
                    if (rightChild.level == 0) {
                        // 右孩子不为空，层数+1
                        rightChild.level = currentLevel + 1;
                    }
                }
                queue.add(rightChild);
            }
        }
    }

    /**
     * 通过广度优先遍历，比较两棵二叉树是否完全一模一样，结构和值
     *
     * @param p
     * @param q
     * @return
     */
    public static boolean compareTwoTreeByBFSTraverse(TreeNode p, TreeNode q) {
        if (p == null && q != null) {
            return false;
        }
        if (p != null && q == null) {
            return false;
        }
        Queue<TreeNode> queueP = new LinkedList<>();
        Queue<TreeNode> queueQ = new LinkedList<>();
        queueP.add(p);
        queueQ.add(q);
        while (true) {
            if (queueP.size() == 0 || queueQ.size() == 0) {
                break;
            }
            // 队首节点出队
            TreeNode currentP = queueP.poll();
            TreeNode currentQ = queueQ.poll();
            if (currentP == null && currentQ != null) {
                return false;
            }
            if (currentP != null && currentQ == null) {
                return false;
            }
            if (currentP == null && currentQ == null) {
                continue;
            }
            if (currentP.val != currentQ.val) {
                return false;
            }

            // 左孩子进队列
            queueP.add(currentP.left);
            queueQ.add(currentQ.left);
            // 右孩子进队列
            queueP.add(currentP.right);
            queueQ.add(currentQ.right);
        }
        if (queueP.isEmpty() && queueQ.isEmpty()) {
            return true;
        }
        return false;
    }

    /**
     * 在二叉树中找到某个唯一节点比指定值大
     *
     * @param
     * @param val
     * @return
     */
    public static TreeNode findOnlyOneNodeMoreThanVal(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val > val) {
            return root;
        }
        TreeNode left = findOnlyOneNodeMoreThanVal(root.left, val);
        TreeNode right = findOnlyOneNodeMoreThanVal(root.right, val);
        if (left != null) {
            return left;
        }
        if (right != null) {
            return right;
        }
        return null;
    }

    /**
     * 在二叉树中找到某个唯一节点比指定值小
     *
     * @param
     * @param val
     * @return
     */
    public static TreeNode findOnlyOneNodeLessThanVal(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val < val) {
            return root;
        }
        TreeNode left = findOnlyOneNodeLessThanVal(root.left, val);
        TreeNode right = findOnlyOneNodeLessThanVal(root.right, val);
        if (left != null) {
            return left;
        }
        if (right != null) {
            return right;
        }
        return null;
    }

    public static TreeNode findTheBiggestNodeInATree(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            return root;
        }
        List<TreeNode> nodeList = new ArrayList<>();
        nodeList.add(root);
        nodeList.add(findTheBiggestNodeInATree(root.left));
        nodeList.add(findTheBiggestNodeInATree(root.right));
        return TreeUtils.theBiggestOneOfNodeList(nodeList);
    }

    private static TreeNode theBiggestOneOfNodeList(List<TreeNode> nodeList) {
        if (nodeList == null || nodeList.size() == 0) {
            return null;
        }
        TreeNode node = new TreeNode();
        node.val = Integer.MIN_VALUE;
        for (TreeNode treeNode : nodeList) {
            if (treeNode == null) {
                continue;
            }
            if (treeNode.val > node.val) {
                node = treeNode;
            }
        }
        return node;
    }

    public static TreeNode findTheLeastNodeInATree(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            return root;
        }
        List<TreeNode> nodeList = new ArrayList<>();
        nodeList.add(root);
        nodeList.add(findTheLeastNodeInATree(root.left));
        nodeList.add(findTheLeastNodeInATree(root.right));
        return TreeUtils.theLeastOneOfNodeList(nodeList);
    }

    private static TreeNode theLeastOneOfNodeList(List<TreeNode> nodeList) {
        if (nodeList == null || nodeList.size() == 0) {
            return null;
        }
        TreeNode node = new TreeNode();
        node.val = Integer.MAX_VALUE;
        for (TreeNode treeNode : nodeList) {
            if (treeNode == null) {
                continue;
            }
            if (treeNode.val < node.val) {
                node = treeNode;
            }
        }
        return node;
    }

    /**
     * 通过BFS判断一颗二叉树是否对称
     *
     * @param root
     * @return
     */
    public static boolean isSymmetricByBFS(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queueLeftToRight = new LinkedList<>();
        Queue<TreeNode> queueRightToleft = new LinkedList<>();
        queueRightToleft.add(root);
        queueLeftToRight.add(root);
        while (true) {
            // 只有当二叉树对称时，才会走break，此时两个队列会同时为空
            if (queueRightToleft.isEmpty() || queueLeftToRight.isEmpty()) {
                break;
            }
            TreeNode treeNodeRightToleft = queueRightToleft.poll();
            TreeNode treeNodeLeftToRight = queueLeftToRight.poll();
            if (treeNodeRightToleft == null && treeNodeLeftToRight != null) {
                return false;
            }
            if (treeNodeRightToleft != null && treeNodeLeftToRight == null) {
                return false;
            }
            if (treeNodeRightToleft == null && treeNodeLeftToRight == null) {
                continue;
            }
            if (treeNodeRightToleft.val != treeNodeLeftToRight.val) {
                return false;
            }
            // 从左到右
            queueLeftToRight.add(treeNodeLeftToRight.left);
            queueLeftToRight.add(treeNodeLeftToRight.right);
            // 从右到左
            queueRightToleft.add(treeNodeRightToleft.right);
            queueRightToleft.add(treeNodeRightToleft.left);
        }
        return true;
    }

    /**
     * 广度优先遍历一棵二叉树，并且将每层的节点加入到一个单独的list中
     * 层次遍历
     *
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrverBFSToLevelList(TreeNode root) {
        // 在结果集中，每一层是一个单独的list，并且resultList[0]表示第一层的结果，resultList[1]表示第二层的结果
        List<List<Integer>> resultList = new ArrayList<>();
        // 根节点为空
        if (root == null) {
            return resultList;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        // 建立节点与层数之间的映射关系
        HashMap<TreeNode, Integer> treeNodeLevelMap = new HashMap<>();
        treeNodeLevelMap.put(root, 1);
        while (queue.size() > 0) {
            // 队首节点出队
            TreeNode currentNode = queue.poll();
            Integer currentNodeLevel = treeNodeLevelMap.get(currentNode);
            // 从map中删除当前出队节点
            treeNodeLevelMap.remove(currentNode);
            // 此处利用了层次遍历，层数是依次递增1的特点
            if (resultList.size() < currentNodeLevel) {
                // 每次遍历到一个新的层时，需要在结果集中添加一个新的list，相当于在结果集中初始化一个新的层来存储层数据
                resultList.add(new ArrayList<>());
            }
            // 将当前节点加入结果集中
            List<Integer> levelList = resultList.get(currentNodeLevel - 1);
            levelList.add(currentNode.val);
            // 将左右孩子加入队列
            if (currentNode.left != null) {
                queue.add(currentNode.left);
                treeNodeLevelMap.put(currentNode.left, currentNodeLevel + 1);
            }
            if (currentNode.right != null) {
                queue.add(currentNode.right);
                treeNodeLevelMap.put(currentNode.right, currentNodeLevel + 1);
            }
        }
        return resultList;
    }

    /**
     * 锯齿形层序遍历（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）
     * <p>
     * 1 3 5 层 左往右
     * <p>
     * 2 4 6 层 右往左
     *
     * @param root
     * @return
     */
    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        // 在结果集中，每一层是一个单独的list，并且resultList[0]表示第一层的结果，resultList[1]表示第二层的结果
        List<List<Integer>> resultList = new ArrayList<>();
        // 根节点为空
        if (root == null) {
            return resultList;
        }
        List<TreeNode> currentNodeList = new ArrayList<>();
        currentNodeList.add(root);
        int currentLevel = 1;
        resultList.add(treeNodeListToVals(currentNodeList));
        while (true) {
            List<TreeNode> newLevelNodes = new ArrayList<>();
            for (int i = currentNodeList.size() - 1; i >= 0; i--) {
                TreeNode currentNode = currentNodeList.get(i);
                if (currentLevel % 2 == 0) {
                    // 当前层是偶数层
                    if (currentNode.left != null) {
                        newLevelNodes.add(currentNode.left);
                    }
                    if (currentNode.right != null) {
                        newLevelNodes.add(currentNode.right);
                    }
                } else {
                    // 当前层是奇数层
                    if (currentNode.right != null) {
                        newLevelNodes.add(currentNode.right);
                    }
                    if (currentNode.left != null) {
                        newLevelNodes.add(currentNode.left);
                    }
                }
            }
            if (newLevelNodes.isEmpty()) {
                break;
            }
            List<Integer> newLevelVals = treeNodeListToVals(newLevelNodes);
            resultList.add(newLevelVals);
            currentNodeList = newLevelNodes;
            currentLevel++;
        }
        return resultList;
    }

    /**
     * 将二叉树节点中所有的值取出来
     *
     * @param currentNodeList
     * @return
     */
    private static List<Integer> treeNodeListToVals(List<TreeNode> currentNodeList) {
        List<Integer> list = new ArrayList<>();
        if (currentNodeList == null || currentNodeList.isEmpty()) {
            return list;
        }
        for (int i = 0; i < currentNodeList.size(); i++) {
            list.add(currentNodeList.get(i).val);
        }
        return list;
    }

    /**
     * 获取一棵二叉树的最大深度
     *
     * @param root
     * @return
     */
    public static int getMaxDeep(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMaxDeep = getMaxDeep(root.left);
        int rightMaxDeep = getMaxDeep(root.right);
        int maxDeep = Math.max(leftMaxDeep, rightMaxDeep) + 1;
        return maxDeep;
    }

    /**
     * 根据前序和中序遍历构建二叉树
     * 规则如下：
     * 1 <= preorder.length <= 3000
     * inorder.length == preorder.length
     * -3000 <= preorder[i], inorder[i] <= 3000
     * preorder和inorder均无重复元素
     * inorder均出现在preorder
     * preorder保证为二叉树的前序遍历序列
     * inorder保证为二叉树的中序遍历序列
     *
     * @param preorder
     * @param inorder
     * @return
     */
    public static TreeNode buildTreeByPreAndInOrder(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0 || preEnd < preStart || inEnd < inStart) {
            return null;
        }
        TreeNode root = new TreeNode();
        root.val = preorder[preStart];
        // 下方注释代码可以不要
//        if (preStart == preEnd || inStart == inEnd) {
//            return root;
//        }
        int rootPositionIndex = getIndexOfValue(inorder, root.val);
//        if (rootPositionIndex == -1) {
//            throw new RuntimeException("在中序遍历没有找到当前所需根节点, " + root.val +
//                    ", 递归函数入参为, " + "preorder = " + Arrays.toString(preorder) + ", preStart = " + preStart + ", preEnd = " + preEnd +
//                    ", inorder = " + Arrays.toString(inorder) + ", inStart = " + inStart + ", inEnd = " + inEnd);
//        }
        int leftTreeLength = rootPositionIndex - inStart;
        root.left = buildTreeByPreAndInOrder(preorder, preStart + 1, preStart + leftTreeLength, inorder, inStart, rootPositionIndex - 1);
        root.right = buildTreeByPreAndInOrder(preorder, preStart + leftTreeLength + 1, preEnd, inorder, rootPositionIndex + 1, inEnd);
        return root;
    }

    private static int getIndexOfValue(int[] inorder, int val) {
        if (inorder == null || inorder.length == 0) {
            return -1;
        }
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 根据后序和中序遍历构建二叉树
     *
     * @param postOrder
     * @param postStart
     * @param postEnd
     * @param inorder
     * @param inStart
     * @param inEnd
     * @return
     */
    public static TreeNode buildTreeByPostAndInOrder(int[] postOrder, int postStart, int postEnd, int[] inorder, int inStart, int inEnd) {
        if (postOrder == null || inorder == null || postOrder.length == 0 || inorder.length == 0 || postEnd < postStart || inEnd < inStart) {
            return null;
        }
        TreeNode root = new TreeNode();
        root.val = postOrder[postEnd];
        // 下方注释代码可以不要
        if (postStart == postEnd || inStart == inEnd) {
            return root;
        }
        int rootPositionIndex = getIndexOfValue(inorder, root.val);
        if (rootPositionIndex == -1) {
            throw new RuntimeException("在中序遍历没有找到当前所需根节点, " + root.val +
                ", 递归函数入参为, " + "preorder = " + Arrays.toString(postOrder) + ", preStart = " + postStart + ", preEnd = " + postEnd +
                ", inorder = " + Arrays.toString(inorder) + ", inStart = " + inStart + ", inEnd = " + inEnd);
        }
        // 计算左子树的长度
        int leftChildTreeLength = rootPositionIndex - inStart;
        root.left = buildTreeByPostAndInOrder(postOrder, postStart, postStart + leftChildTreeLength - 1, inorder, inStart, rootPositionIndex - 1);
        root.right = buildTreeByPostAndInOrder(postOrder, postStart + leftChildTreeLength, postEnd - 1, inorder, rootPositionIndex + 1, inEnd);
        return root;
    }

    /**
     * 自底向上的层序遍历（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
     *
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrderFromBottomToTop(TreeNode root) {
        List<List<Integer>> resultSet = new ArrayList<>();
        if (root == null) {
            return resultSet;
        }
        List<TreeNode> currentLevelNodes = new ArrayList<>();
        currentLevelNodes.add(root);
        List<Integer> currentLevelValues = treeNodeListToVals(currentLevelNodes);
        if (root.left == null && root.right == null) {
            resultSet.add(currentLevelValues);
            return resultSet;
        }
        Stack<List<Integer>> resultSetStack = new Stack<>();
        resultSetStack.add(currentLevelValues);
        while (true) {
            List<TreeNode> newLevelNodes = new ArrayList<>();
            // 遍历当前层，得到新的层
            for (int i = 0; i < currentLevelNodes.size(); i++) {
                TreeNode currentNode = currentLevelNodes.get(i);
                if (currentNode.left != null) {
                    newLevelNodes.add(currentNode.left);
                }
                if (currentNode.right != null) {
                    newLevelNodes.add(currentNode.right);
                }
            }
            if (newLevelNodes.isEmpty()) {
                break;
            }
            resultSetStack.add(treeNodeListToVals(newLevelNodes));
            currentLevelNodes = newLevelNodes;
        }
        while (!resultSetStack.isEmpty()) {
            resultSet.add(resultSetStack.pop());
        }
        return resultSet;
    }

    /**
     * 根据一个整数数组 nums ，其中元素已经按 升序 排列，将其转换为一棵 高度平衡 二叉搜索树。
     * <p>
     * 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
     *
     * @param nums
     * @return
     */
    public static TreeNode generateAVLBySortedArray(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }
        if (start == end) {
            return new TreeNode(nums[start]);
        }
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = generateAVLBySortedArray(nums, start, mid - 1);
        root.right = generateAVLBySortedArray(nums, mid + 1, end);
        return root;
    }

    public static TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        List<Integer> list = new ArrayList<>();
        ListNode curNode = head;
        while (curNode != null) {
            list.add(curNode.val);
            curNode = curNode.next;
        }
        Integer[] array = list.toArray(new Integer[0]);
        int left = 0;
        int right = array.length - 1;
        return solveSortedListToBST(left, right, array);
    }

    private static TreeNode solveSortedListToBST(int left, int right, Integer[] array) {
        if (left > right || left < 0 || left > array.length - 1 || right < 0 || right > array.length - 1) {
            return null;
        }
        if (left == right) {
            return new TreeNode(array[left]);
        }
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(array[mid]);
        root.left = solveSortedListToBST(left, mid - 1, array);
        root.right = solveSortedListToBST(mid + 1, right, array);
        return root;
    }

    public static void BFS(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode curNode = queue.poll();
            System.out.println(curNode.val);
            if (curNode.left != null) {
                queue.add(curNode.left);
            }
            if (curNode.right != null) {
                queue.add(curNode.right);
            }
        }
    }

    public static void DFS(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode curNode = stack.pop();  // 取栈顶元素
            System.out.println(curNode.val);  // 输出取到的当前元素
            if (curNode.right != null) {
                stack.push(curNode.right);
            }
            if (curNode.left != null) {
                stack.push(curNode.left);
            }
        }
    }

    /**
     * 生成值在 [start, end] 范围之内随机数的二叉树
     *
     * @param start
     * @param end
     * @param count
     * @return
     */
    public static TreeNode generateAtreeByRandomVal(int start, int end, int count) {
        if (start > end) {
            return null;
        }
        if (count <= 0) {
            return null;
        }
        int num = 0;
        Random random = new Random();
        TreeNode root = new TreeNode();
        root.val = random.nextInt(end - start + 1) + start;
        root.level = 1;
        num++;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (true) {
            TreeNode curNode = queue.poll();
            if (num < count) {
                TreeNode newNode = new TreeNode();
                newNode.val = random.nextInt(end - start + 1) + start;
                newNode.level = curNode.level + 1;
                curNode.left = newNode;
                queue.add(newNode);
                num++;
            } else {
                break;
            }
            if (num < count) {
                TreeNode newNode = new TreeNode();
                newNode.val = random.nextInt(end - start + 1) + start;
                newNode.level = curNode.level + 1;
                curNode.right = newNode;
                queue.add(newNode);
                num++;
            } else {
                break;
            }
        }
        return root;
    }

    public static List<Integer> getLeetcodeTreeVals(TreeNode root) {
        List<Integer> vals = new ArrayList<>();
        if (root == null) {
            return vals;
        }
        if (root.left == null && root.right == null) {
            vals.add(root.val);
            return vals;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode curNode = queue.poll();
            if (curNode != null) {
                vals.add(curNode.val);
            } else {
                vals.add(null);
                continue;
            }
            if (curNode.left == null && curNode.right == null) {
                continue;
            }
            queue.add(curNode.left);
            queue.add(curNode.right);
        }
        if (!vals.isEmpty() && vals.get(vals.size() - 1) == null) {
            vals.remove(vals.size() - 1);
        }
        return vals;
    }

    public static List<Integer> leetcodeStandardOutputForBinaryTreeForNode(Node root) {
        List<Integer> vals = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            if (curNode != null) {
                vals.add(curNode.val);
            } else {
                vals.add(null);
                continue;
            }
            if (curNode.left == null && curNode.right == null) {
                continue;
            }
            queue.add(curNode.left);
            queue.add(curNode.right);
        }
        if (!vals.isEmpty() && vals.get(vals.size() - 1) == null) {
            vals.remove(vals.size() - 1);
        }
        return vals;
    }

    public static List<String> leetcodeSpecialStandardOutputForBinaryTreeForNode(Node root) {
        List<String> vals = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            if (curNode != null) {
                vals.add(String.valueOf(curNode.val));
                if (curNode.next == null) {
                    vals.add("#");
                }
            } else {
//                vals.add(null);
                continue;
            }
            if (curNode.left == null && curNode.right == null) {
                continue;
            }
            queue.add(curNode.left);
            queue.add(curNode.right);
        }
        if (!vals.isEmpty() && vals.get(vals.size() - 1) == null) {
            vals.remove(vals.size() - 1);
        }
        return vals;
    }

    public static boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (root.left == null && root.right == null) {
            return true;
        }
        int left = getTreeHeight(root.left);
        int right = getTreeHeight(root.right);
        if (Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right)) {
            return true;
        } else {
            return false;
        }
    }

    private static int getTreeHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return Math.max(getTreeHeight(root.left), getTreeHeight(root.right)) + 1;
    }

    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        solvePreorderTraversal(result, root);
        return result;
    }

    private static void solvePreorderTraversal(List<Integer> result, TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            result.add(root.val);
            return;
        }
        result.add(root.val);
        solvePreorderTraversal(result, root.left);
        solvePreorderTraversal(result, root.right);
    }

    public static List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        solvePostorderTraversal(result, root);
        return result;
    }

    private static void solvePostorderTraversal(List<Integer> result, TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            result.add(root.val);
            return;
        }
        solvePostorderTraversal(result, root.left);
        solvePostorderTraversal(result, root.right);
        result.add(root.val);
    }

    public static int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        if (root.left == null) {
            return minDepth(root.right) + 1;
        }
        if (root.right == null) {
            return minDepth(root.left) + 1;
        }
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }

    public static List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        if (root.left == null && root.right == null) {
            String s = String.valueOf(root.val);
            result.add(s);
            return result;
        }
        List<String> leftPaths = binaryTreePaths(root.left);
        List<String> rightPaths = binaryTreePaths(root.right);
        for (int i = 0; i < leftPaths.size(); i++) {
            result.add(root.val + "->" + leftPaths.get(i));
        }
        for (int i = 0; i < rightPaths.size(); i++) {
            result.add(root.val + "->" + rightPaths.get(i));
        }
        return result;
    }

    public static TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            return root;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    public static List<Integer> preorder(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        if (root.children == null || root.children.isEmpty()) {
            result.add(root.val);
            return result;
        }
        solvePreorder(result, root);
        return result;
    }

    private static void solvePreorder(List<Integer> result, Node root) {
        if (root == null) {
            return;
        }
        if (root.children == null || root.children.isEmpty()) {
            result.add(root.val);
            return;
        }
        result.add(root.val);
        for (Node child : root.children) {
            solvePreorder(result, child);
        }
    }

    public static List<Integer> postorder(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        if (root.children == null || root.children.isEmpty()) {
            result.add(root.val);
            return result;
        }
        solvePostorder(result, root);
        return result;
    }

    private static void solvePostorder(List<Integer> result, Node root) {
        if (root == null) {
            return;
        }
        if (root.children == null || root.children.isEmpty()) {
            result.add(root.val);
            return;
        }
        for (Node child : root.children) {
            solvePostorder(result, child);
        }
        result.add(root.val);
    }

    public static boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return traverseTree(root, subRoot);
    }

    private static boolean traverseTree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null || subRoot == null) {
            return false;
        }
        if (root.val == subRoot.val && comparePreList(root, subRoot) && compareMidList(root, subRoot)) {
            return true;
        }
        boolean left = false;
        boolean right = false;
        if (root.left != null) {
            left = traverseTree(root.left, subRoot);
        }
        if (root.right != null) {
            right = traverseTree(root.right, subRoot);
        }
        return left || right;
    }

    private static boolean compareMidList(TreeNode root, TreeNode subRoot) {
        List<Integer> rootMidList = midTraverse(root);
        List<Integer> subMidList = midTraverse(subRoot);
        if (rootMidList.size() != subMidList.size()) {
            return false;
        } else {
            for (int i = 0; i < rootMidList.size(); i++) {
                if (!rootMidList.get(i).equals(subMidList.get(i))) {
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean comparePreList(TreeNode root, TreeNode subRoot) {
        List<Integer> rootPreList = preTraverse(root);
        List<Integer> subPreList = preTraverse(subRoot);
        if (rootPreList.size() != subPreList.size()) {
            return false;
        } else {
            for (int i = 0; i < rootPreList.size(); i++) {
                if (!rootPreList.get(i).equals(subPreList.get(i))) {
                    return false;
                }
            }
        }
        return true;
    }

    public static List<Integer> midTraverse(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        if (root.left == null && root.right == null) {
            list.add(root.val);
            return list;
        }
        getMidTraverseList(list, root);
        return list;
    }

    private static void getMidTraverseList(List<Integer> list, TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            list.add(root.val);
            return;
        }
        getMidTraverseList(list, root.left);
        list.add(root.val);
        getMidTraverseList(list, root.right);
    }

    public static List<Integer> preTraverse(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        if (root.left == null && root.right == null) {
            list.add(root.val);
            return list;
        }
        getPreTraverseList(list, root);
        return list;
    }

    private static void getPreTraverseList(List<Integer> list, TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            list.add(root.val);
            return;
        }
        list.add(root.val);
        getPreTraverseList(list, root.left);
        getPreTraverseList(list, root.right);
    }

    public static int[] findMode(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        if (root.left == null && root.right == null) {
            int[] result = new int[1];
            result[0] = root.val;
            return result;
        }
        Map<Integer, Integer> map = new HashMap<>();
        countByTraverse(map, root);
        int maxCount = 0;
        for (Integer num : map.keySet()) {
            maxCount = Math.max(maxCount, map.get(num));
        }
        List<Integer> list = new ArrayList<>();
        for (Integer num : map.keySet()) {
            if (map.get(num) == maxCount) {
                list.add(num);
            }
        }
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }

    private static void countByTraverse(Map<Integer, Integer> map, TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            map.merge(root.val, 1, Integer::sum);
            return;
        }
        map.merge(root.val, 1, Integer::sum);
        countByTraverse(map, root.left);
        countByTraverse(map, root.right);
    }

    public static int getMinimumDifference(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        getSearchTreeList(root, list);
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < list.size(); i++) {
            min = Math.min(min, Math.abs(list.get(i) - list.get(i - 1)));
        }
        return min;
    }

    private static void getSearchTreeList(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            list.add(root.val);
            return;
        }
        getSearchTreeList(root.left, list);
        list.add(root.val);
        getSearchTreeList(root.right, list);
    }

    public static int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 0;
        }
        int[] ans = {0};
        resolveDiameter(root, ans);
        return ans[0];
    }

    private static int resolveDiameter(TreeNode root, int[] ans) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int left = resolveDiameter(root.left, ans);
        int right = resolveDiameter(root.right, ans);
        ans[0] = Math.max(ans[0], left + right);
        return Math.max(left, right) + 1;
    }

    public static int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }
        if (root.children == null || root.children.isEmpty()) {
            return 1;
        }
        int childDepth = 0;
        for (Node child : root.children) {
            childDepth = Math.max(childDepth, maxDepth(child));
        }
        return childDepth + 1;
    }

    public static int findTilt(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 0;
        }
        List<Integer> list = new ArrayList<>();
        solveFindTilt(list, root);
        return list.stream().reduce(Integer::sum).orElse(0);
    }

    private static int solveFindTilt(List<Integer> list, TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return root.val;
        }
        int leftSum = solveFindTilt(list, root.left);
        int rightSum = solveFindTilt(list, root.right);
        list.add(Math.abs(leftSum - rightSum));
        return leftSum + rightSum + root.val;
    }

    public static int findSecondMinimumValue(TreeNode root) {
        if (root == null) {
            return -1;
        }
        List<Integer> list = new ArrayList<>();
        getPreTraverseList(list, root);
        List<Integer> result = list.stream().distinct().sorted().collect(Collectors.toList());
        if (result.size() < 2) {
            return -1;
        }
        return result.get(1);
    }

    public static boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> leafList1 = new ArrayList<>();
        List<Integer> leafList2 = new ArrayList<>();
        getLeafListByPreOrderTraverse(leafList1, root1);
        getLeafListByPreOrderTraverse(leafList2, root2);
        if (leafList1.size() != leafList2.size()) {
            return false;
        } else {
            for (int i = 0; i < leafList1.size(); i++) {
                if (!Objects.equals(leafList1.get(i), leafList2.get(i))) {
                    return false;
                }
            }
        }
        return true;
    }

    private static void getLeafListByPreOrderTraverse(List<Integer> leafList, TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            leafList.add(root.val);
            return;
        }
        getLeafListByPreOrderTraverse(leafList, root.left);
        getLeafListByPreOrderTraverse(leafList, root.right);
    }

    public static TreeNode increasingBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            return root;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        addNodeToQueue(queue, root);
        TreeNode queueHead = queue.poll();
        if (queueHead != null) {
            queueHead.left = null;
            queueHead.right = null;
        }
        TreeNode newRoot = queueHead;
        TreeNode curNode = newRoot;
        while (!queue.isEmpty()) {
            queueHead = queue.poll();
            queueHead.left = null;
            queueHead.right = null;
            curNode.right = queueHead;
            curNode = curNode.right;
        }
        return newRoot;
    }

    private static void addNodeToQueue(Queue<TreeNode> queue, TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            queue.add(root);
            return;
        }
        addNodeToQueue(queue, root.left);
        queue.add(root);
        addNodeToQueue(queue, root.right);
    }

    public static int rangeSumBST(TreeNode root, int low, int high) {
        List<Integer> list = new ArrayList<>();
        getSearchTreeList(root, list);
        int sum = 0;
        for (Integer num : list) {
            if (num < low) {
                continue;
            }
            if (num > high) {
                break;
            }
            sum += num;
        }
        return sum;
    }

    public static String tree2str(TreeNode root) {
        if (root == null) {
            return "";
        }
        if (root.left == null && root.right == null) {
            return String.valueOf(root.val);
        }
        StringBuilder result = new StringBuilder();
        getStringByPreTraverse(result, root);
        return result.toString();
    }

    private static void getStringByPreTraverse(StringBuilder result, TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            result.append(root.val);
            return;
        }
        result.append(root.val);
        if (root.left == null) {
            result.append("()");
        } else {
            result.append("(");
            getStringByPreTraverse(result, root.left);
            result.append(")");
        }
        if (root.right != null) {
            result.append("(");
            getStringByPreTraverse(result, root.right);
            result.append(")");
        }
    }

    public static boolean findTarget(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        getSearchTreeList(root, list);
        int left = 0;
        int right = list.size() - 1;
        while (left < right) {
            int sum = list.get(left) + list.get(right);
            if (sum == k) {
                return true;
            } else if (sum > k) {
                right--;
            } else {
                left++;
            }
        }
        return false;
    }

    public static boolean isCousins(TreeNode root, int x, int y) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            boolean showX = false;
            boolean showY = false;
            for (int i = 0; i < levelSize; i++) {
                TreeNode curNode = queue.poll();
                if (curNode == null) {
                    continue;
                }
                boolean lx = checkValue(curNode.left, x);
                boolean rx = checkValue(curNode.right, x);
                boolean ly = checkValue(curNode.left, y);
                boolean ry = checkValue(curNode.right, y);
                // 同时有 x 和 y
                if ((lx || rx) && (ly || ry)) {
                    return false;
                } else {
                    if (!showX && lx || rx) {
                        showX = true;
                    }
                    if (!showY && ly || ry) {
                        showY = true;
                    }
                    if (showX && showY) {
                        return true;
                    }
                }
                if (curNode.left != null) {
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
        }
        return false;
    }

    private static boolean checkValue(TreeNode left, int value) {
        return left != null && left.val == value;
    }

    public static void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        getPreTraverseNodeList(list, root);
        TreeNode[] nodes = list.toArray(new TreeNode[0]);
        for (int i = 0; i < nodes.length; i++) {
            nodes[i].left = null;
            if (i != nodes.length - 1) {
                nodes[i].right = nodes[i + 1];
            } else {
                nodes[i].right = null;
            }
        }
    }


    private static void getPreTraverseNodeList(List<TreeNode> list, TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            list.add(root);
            return;
        }
        list.add(root);
        getPreTraverseNodeList(list, root.left);
        getPreTraverseNodeList(list, root.right);
    }

    public static int kthSmallest(TreeNode root, int k) {
        List<Integer> list = midTraverse(root);
        return list.get(k - 1);
    }

    private static void getMidTraverseNodeList(List<TreeNode> list, TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            list.add(root);
            return;
        }
        getMidTraverseNodeList(list, root.left);
        list.add(root);
        getMidTraverseNodeList(list, root.right);
    }

    public static TreeNode convertBST(TreeNode root) {
        List<TreeNode> list = getTreeNodesByMidTraverse(root);
        TreeNode[] nodes = list.toArray(new TreeNode[0]);
        for (int i = nodes.length - 2; i >= 0; i--) {
            nodes[i].val += nodes[i + 1].val;
        }
        return root;
    }

    public static List<TreeNode> getTreeNodesByMidTraverse(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        getMidTraverseNodeList(list, root);
        return list;
    }

    public static TreeNode removeLeafNodes(TreeNode root, int target) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            if (root.val == target) {
                return null;
            } else {
                return root;
            }
        }
        root.left = removeLeafNodes(root.left, target);
        root.right = removeLeafNodes(root.right, target);
        if (root.left == null && root.right == null) {
            if (root.val == target) {
                return null;
            } else {
                return root;
            }
        }
        return root;
    }

    public static TreeNode getTreeNodeByVal(TreeNode root, int targetVal) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            if (root.val == targetVal) {
                return root;
            } else {
                return null;
            }
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode curNode = queue.poll();
            if (curNode.val == targetVal) {
                return curNode;
            }
            if (curNode.left != null) {
                queue.add(curNode.left);
            }
            if (curNode.right != null) {
                queue.add(curNode.right);
            }
        }
        return null;
    }

    public static int goodNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int[] count = new int[1];
        List<Integer> curPath = new ArrayList<>();
        solveGoodNodes(count, curPath, root);
        return count[0];
    }

    private static void solveGoodNodes(int[] count, List<Integer> curPath, TreeNode root) {
        if (root == null) {
            return;
        }
        boolean pass = false;
        for (Integer num : curPath) {
            if (num > root.val) {
                pass = true;
                break;
            }
        }
        if (!pass) {
            count[0]++;
        }
        curPath.add(root.val);
        solveGoodNodes(count, curPath, root.left);
        solveGoodNodes(count, curPath, root.right);
        curPath.remove(curPath.size() - 1);
    }

    public static int averageOfSubtree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int[] result = new int[1];
        solveAverageOfSubtree(result, root);
        return result[0];
    }

    private static Pair<Integer, Integer> solveAverageOfSubtree(int[] result, TreeNode root) {
        if (root == null) {
            // key 为 和, value 为 数量
            return new Pair<>(0, 0);
        }
        if (root.left == null && root.right == null) {
            result[0]++;
            return new Pair<>(root.val, 1);
        }
        Pair<Integer, Integer> leftPair = solveAverageOfSubtree(result, root.left);
        Pair<Integer, Integer> rightPair = solveAverageOfSubtree(result, root.right);
        int subTreeSum = leftPair.getKey() + rightPair.getKey() + root.val;
        int subTreeCount = leftPair.getValue() + rightPair.getValue() + 1;
        if (Math.floor(subTreeSum / subTreeCount) == root.val) {
            result[0]++;
        }
        return new Pair<>(subTreeSum, subTreeCount);
    }

    public static int countUnivalSubtrees(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int[] result = new int[1];
        solveCountUnivalSubtrees(root, result);
        return result[0];
    }

    private static boolean solveCountUnivalSubtrees(TreeNode root, int[] result) {
        if (root == null) {
            return true;
        }
        if (root.left == null && root.right == null) {
            result[0]++;
            return true;
        }
        boolean left = solveCountUnivalSubtrees(root.left, result);
        boolean right = solveCountUnivalSubtrees(root.right, result);
        if (left && right) {
            if (root.left != null && root.right != null) {
                if (root.left.val == root.val && root.right.val == root.val) {
                    result[0]++;
                    return true;
                }
            } else {
                if (root.left != null && root.left.val == root.val) {
                    result[0]++;
                    return true;
                }
                if (root.right != null && root.right.val == root.val) {
                    result[0]++;
                    return true;
                }
            }
        }
        return false;
    }

    public static int closestValue(TreeNode root, double target) {
        if (root.left == null && root.right == null) {
            return root.val;
        }
        Result result = new Result();
        result.value = root.val;
        solveClosestValue(target, root, result);
        return result.value;
    }

    private static void solveClosestValue(double target, TreeNode root, Result result) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            if (Math.abs(root.val - target) < Math.abs(result.value - target)) {
                result.value = root.val;
            }
            return;
        }
        if (Math.abs(root.val - target) < Math.abs(result.value - target)) {
            result.value = root.val;
        }
        solveClosestValue(target, root.left, result);
        solveClosestValue(target, root.right, result);
    }

    public static int largestBSTSubtree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int[] result = new int[1];
        solveLargestBSTSubtree(root, result);
        return result[0];
    }

    private static TreeNodeInfo solveLargestBSTSubtree(TreeNode root, int[] result) {
        if (root == null) {
            result[0] = Math.max(0, result[0]);
            return new TreeNodeInfo(true, 0, null, null);
        }
        // 左右子树都没有
        if (root.left == null && root.right == null) {
            result[0] = Math.max(1, result[0]);
            return new TreeNodeInfo(true, 1, root.val, root.val);
        }
        TreeNodeInfo left = solveLargestBSTSubtree(root.left, result);
        TreeNodeInfo right = solveLargestBSTSubtree(root.right, result);
        // 左右子树都是BST树
        if (left.isBST && right.isBST) {
            // 左右子树都有
            if (root.left != null && root.right != null) {
                if (root.val > left.max && root.val < right.min) {
                    result[0] = Math.max(left.count + right.count + 1, result[0]);
                    return new TreeNodeInfo(true, left.count + right.count + 1, left.min, right.max);
                }
            } else if (root.left == null && root.right != null) {
                // 只有右子树
                if (root.val < right.min) {
                    result[0] = Math.max(left.count + right.count + 1, result[0]);
                    return new TreeNodeInfo(true, left.count + right.count + 1, root.val, right.max);
                }
            } else {
                // 只有左子树
                if (root.val > left.max) {
                    result[0] = Math.max(left.count + right.count + 1, result[0]);
                    return new TreeNodeInfo(true, left.count + right.count + 1, left.min, root.val);
                }
            }
        }
        int min;
        int max;
        // 左右子树都有
        if (root.left != null && root.right != null) {
            min = Math.min(Math.min(left.min, right.min), root.val);
            max = Math.max(Math.max(left.max, right.max), root.val);
        } else if (root.left == null && root.right != null) {
            // 只有右子树
            min = Math.min(right.min, root.val);
            max = Math.max(right.max, root.val);
        } else {
            // 只有左子树
            min = Math.min(left.min, root.val);
            max = Math.max(left.max, root.val);
        }
        return new TreeNodeInfo(false, left.count + right.count + 1, min, max);
    }

    public static TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        List<TreeNode> treeNodes = getTreeNodesByMidTraverse(root);
        int left = 0;
        int right = treeNodes.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (treeNodes.get(mid).val == p.val) {
                if (mid + 1 < treeNodes.size()) {
                    return treeNodes.get(mid + 1);
                } else {
                    return null;
                }
            } else if (treeNodes.get(mid).val < p.val) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return null;
    }

    public static boolean evaluateTree(TreeNode root) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return root.val == 0 ? false : true;
        }
        if (root.val == 2) {
            return evaluateTree(root.left) || evaluateTree(root.right);
        } else if (root.val == 3) {
            return evaluateTree(root.left) && evaluateTree(root.right);
        }
        return false;
    }

    public static TreeNode constructMaximumBinaryTree(int[] nums) {
        return resolveMaxTree(nums, 0, nums.length - 1);
    }

    private static TreeNode resolveMaxTree(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        if (left == right) {
            return new TreeNode(nums[left]);
        }
        int index = left;
        int maxNum = nums[left];
        for (int i = left; i <= right; i++) {
            if (nums[i] > maxNum) {
                maxNum = nums[i];
                index = i;
            }
        }
        TreeNode root = new TreeNode(maxNum);
        root.left = resolveMaxTree(nums, left, index - 1);
        root.right = resolveMaxTree(nums, index + 1, right);
        return root;
    }

    public static TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            return root;
        }
        swapTreeChildNodes(root);
        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;
    }

    private static void swapTreeChildNodes(TreeNode root) {
        TreeNode temp;
        temp = root.left;
        root.left = root.right;
        root.right = temp;
    }

    public static int maxAncestorDiff2(TreeNode root) {
        int[] ans = new int[1];
        resolveMaxAncestorDiff(ans, root);
        return ans[0];
    }

    private static Set<Integer> resolveMaxAncestorDiff(int[] ans, TreeNode root) {
        if (root == null) {
            return new HashSet<>();
        }
        if (root.left == null && root.right == null) {
            Set<Integer> set = new HashSet<>();
            set.add(root.val);
            return set;
        }
        // 不用获取所有节点，只要得到最大最小节点即可
        Set<Integer> set = new HashSet<>();
        if (root.left != null) {
            Set<Integer> leftVals = resolveMaxAncestorDiff(ans, root.left);
            updateDate(ans, root, set, leftVals);
        }
        if (root.right != null) {
            Set<Integer> rightVals = resolveMaxAncestorDiff(ans, root.right);
            updateDate(ans, root, set, rightVals);
        }
        set.add(root.val);
        return set;
    }

    private static void updateDate(int[] ans, TreeNode root, Set<Integer> set, Set<Integer> leftVals) {
        if (!leftVals.isEmpty()) {
            set.addAll(leftVals);
        }
        for (Integer num : set) {
            int val = Math.abs(root.val - num);
            if (val > ans[0]) {
                ans[0] = val;
            }
        }
    }

    public static int maxAncestorDiff(TreeNode root) {
        return resolveMaxAncestorDiff2(root, root.val, root.val);
    }

    public static int resolveMaxAncestorDiff2(TreeNode root, int mi, int ma) {
        if (root == null) {
            return 0;
        }
        int diff = Math.max(Math.abs(root.val - mi), Math.abs(root.val - ma));
        mi = Math.min(mi, root.val);
        ma = Math.max(ma, root.val);
        diff = Math.max(diff, resolveMaxAncestorDiff2(root.left, mi, ma));
        diff = Math.max(diff, resolveMaxAncestorDiff2(root.right, mi, ma));
        return diff;
    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        boolean[] pq = {false, false};
        return resolveCommonAncestor(root, pq, p, q);
    }

    private static TreeNode resolveCommonAncestor(TreeNode root, boolean[] pq, TreeNode p, TreeNode q) {
        boolean pp = pq[0];
        boolean qq = pq[1];
        if (root == null) {
            return null;
        }
        if (!pq[0] && root.val == p.val) {
            pq[0] = true;
        } else if (!pq[1] && root.val == q.val) {
            pq[1] = true;
        }
        TreeNode left = resolveCommonAncestor(root.left, pq, p, q);
        if (!pp && !qq && left != null) {
            return left;
        }
        TreeNode right = resolveCommonAncestor(root.right, pq, p, q);
        if (!pp && !qq && right != null) {
            return right;
        }
        if (!pp && !qq && pq[0] && pq[1]) {
            return root;
        }
        return null;
    }

    public static boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (root.left == null && root.right == null) {
            return true;
        }
        return compareNode(root.left, root.right);
    }

    private static boolean compareNode(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) {
            return true;
        }
        if (node1 == null || node2 == null) {
            return false;
        }
        return compareNode(node1.left, node2.right) && compareNode(node1.right, node2.left) && node1.val == node2.val;
    }

    public static double maximumAverageSubtree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return root.val;
        }
        double[] ans = {Double.MIN_VALUE};
        resolveMaximumAverageSubtree(root, ans);
        return ans[0];
    }

    /**
     * 返回数组 int[0] 是子树所有值的和
     * int[1] 是子树节点的
     *
     * @param root
     * @param ans
     * @return
     */
    private static int[] resolveMaximumAverageSubtree(TreeNode root, double[] ans) {
        if (root == null) {
            return new int[]{0, 0};
        }
        if (root.left == null && root.right == null) {
            if (root.val > ans[0]) {
                ans[0] = root.val;
            }
            return new int[]{root.val, 1};
        }
        int[] left = resolveMaximumAverageSubtree(root.left, ans);
        int[] right = resolveMaximumAverageSubtree(root.right, ans);
        int sum = left[0] + right[0] + root.val;
        int count = left[1] + right[1] + 1;
        double num = sum * 1.0 / count;
        if (num > ans[0]) {
            ans[0] = num;
        }
        return new int[]{sum, count};
    }

    /**
     * 二叉树的垂直遍历
     *
     * @param root
     * @return
     */
    public static List<List<Integer>> verticalOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        bfs(root, map);
        return getResult(map);
    }

    private static List<List<Integer>> getResult(Map<Integer, List<Integer>> map) {
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < 200; i++) {
            if (map.get(i) != null) {
                result.add(map.get(i));
            }
        }
        return result;
    }

    /**
     * 树中结点的数目在范围 [0, 100] 内
     *
     * @param root
     * @param map
     */
    private static void bfs(TreeNode root, Map<Integer, List<Integer>> map) {
        Queue<Pair<Integer, TreeNode>> queue = new LinkedList<>();
        // 根节点集合id设置为100即可
        queue.add(new Pair<>(100, root));
        while (queue.size() > 0) {
            Pair<Integer, TreeNode> treeNodePair = queue.poll();
            Integer curNodeId = treeNodePair.getKey();
            TreeNode curNode = treeNodePair.getValue();
            map.putIfAbsent(curNodeId, new ArrayList<>());
            map.get(curNodeId).add(curNode.val);
            if (curNode.left != null) {
                queue.add(new Pair<>(curNodeId - 1, curNode.left));
            }
            if (curNode.right != null) {
                queue.add(new Pair<>(curNodeId + 1, curNode.right));
            }
        }
    }

    public static boolean checkTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (root.left == null && root.right == null) {
            return true;
        }
        if (root.left == null && root.val == root.right.val || root.right == null && root.val == root.left.val) {
            return true;
        }
        if (root.val == root.left.val + root.right.val) {
            return checkTree(root.left) && checkTree(root.right);
        }
        return false;
    }

    public static List<Integer> getLonelyNodes1(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        if (root.left == null && root.right == null) {
            return result;
        } else if (root.right != null && root.left == null) {
            result.add(root.right.val);
        } else if (root.right == null && root.left != null) {
            result.add(root.left.val);
        }
        List<Integer> leftNodes = getLonelyNodes(root.left);
        List<Integer> rightNodes = getLonelyNodes(root.right);
        if (leftNodes.size() > 0) {
            result.addAll(leftNodes);
        }
        if (rightNodes.size() > 0) {
            result.addAll(rightNodes);
        }
        return result;
    }

    public static List<Integer> getLonelyNodes(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        getLonelyNodes(root, result);
        return result;
    }

    public static void getLonelyNodes(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            return;
        } else if (root.right != null && root.left == null) {
            result.add(root.right.val);
        } else if (root.right == null && root.left != null) {
            result.add(root.left.val);
        }
        getLonelyNodes(root.left, result);
        getLonelyNodes(root.right, result);
    }
}
















